package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 描述：
 * <p>
 * 解题思路:
 * 穷举：
 * 穷举每种可能 最终得出最大的点数
 * 结果:超出内存限制
 * <p>
 * 优化1:比较k的值与数组长度
 * 如果k的值小于数组长度的一半 则正向穷举
 * 如果k的值大于数组长度的一半 则找出最小的连续和
 * <p>
 * 优化2:考虑使用动态规划 可以使用map存储k-1的所有值可能性
 * <p>
 * 优化3: 将所有数围成一个圈
 * 随便选出一个起点坐标 k值固定 则选择范围固定 不断移动起点 直到最终回到起点 比较所有可能性中的最大值
 * 时间复杂度:n
 * 空间复杂度:1
 *
 * @author 🧑 ‍wanwei
 * @since 2022-10-27 16:06
 */
public class CL1423可获得的最大点数 {


    public static void main(String[] args) {
        int[] cardPoints = {1,2,3,4,5,6,1};
        int k = 3;
        System.out.println(maxScore2(cardPoints, k));
    }

    public static int maxScore2(int[] cardPoints, int k) {
        int [] cardPointsNew = Arrays.copyOf(cardPoints,cardPoints.length*2);
        System.arraycopy(cardPoints,0,cardPointsNew,cardPoints.length,cardPoints.length);

        int max = 0;
        int lastNum = 0;
        for (int i = cardPoints.length - k; i <= cardPoints.length; i++) {
            int total = 0;
            //第一次计算累加和 后面的数只需要在之前的基础上减去上一个值 加上下一个值即可
            if(i == cardPoints.length - k){
                for (int j = i; j < i+k; j++) {
                    total += cardPointsNew[j];
                }
                lastNum = total;
            }else {
                total = lastNum - cardPointsNew[i - 1] + cardPointsNew[i+k -1];
                lastNum = total;
            }
            max = max > total?max:total;
        }
        return max;
    }


    public static int maxScore(int[] cardPoints, int k) {
        List<Integer> list = new ArrayList<>();
        int left = -1;
        int right = cardPoints.length;
        maxScoreLast(cardPoints, k, left, right, list);
        return list.get(0);
    }

    private static void maxScoreLast(int[] cardPoints, int k, int left, int right, List<Integer> list) {
        if (cardPoints.length - (right - left - 1) == k || right <= left) {
            int total = 0;
            for (int i = 0; i <= left; i++) {
                total += cardPoints[i];
            }
            for (int i = right; i < cardPoints.length; i++) {
                total += cardPoints[i];
            }
            list.add(total);
            if (list.size() > 1 && total > list.get(0)) {
                list.set(0, total);
            }
            return;
        }
        maxScoreLast(cardPoints, k, left + 1, right, list);
        maxScoreLast(cardPoints, k, left, right - 1, list);

    }
}
